package com.mamingchao.basic.swardToOffer.three;

import java.util.Arrays;

/**
 * 题目：过沼泽地
 * 小红来到一片沼泽地的岸边，她希望通过这边沼泽地
 * 这片沼泽地用一个矩阵表示，1表示沼泽，0表示平地；小红刚开始在矩阵的左上角，她需要在右下角离开地图；已知 进入地图和离开地图的时间可以忽略。
 *
 * 小红可以向左、向右 和向下走
 *
 * 当小红从沼泽进入沼泽，或者平地进入平地，需要花费1单位时间
 * 当小红从沼泽进入平地，或者平地进入沼泽，由于需要更换装备，所以需要花费2单位时间
 *
 * 小红从左上角进入地图，右下角离开地图；现在，小红想知道，经过这片沼泽，最少花费多少单位时间
 *
 * 输入描述：
 *     矩阵输入：第一行输入两个正整数，n 和 m ，用空格隔开 代表矩阵的行数和列数
 *     接下来的n行，每行输入m个正整数，a，用来表示矩阵
 *     2 <= n,m <=500 , 0 <= a <= 1
 *
 * 这个问题跟象棋的那个题很相似；用动态规划实现
 *
 *  0 1 0 0 1
 *  1 0 1 0 1
 *  1 1 0 0 1
 *  1 0 0 0 0
 */
public class CrossMarshland {

    public static void main(String[] args) {

        final int n = 50;
        final int m = 40;

        int[][] matric = new int[n][m];
        for (int i = 0; i < n ; i++) {
            for (int j = 0; j < m; j++) {
                matric[i][j] = (i+j)%2;
            }
        }

//        int result = getSteps(0,0,0,matric);
//        System.out.println(result);

        int result1= getStepsWithDp(n,m,matric);
        System.out.println(result1);
    }
    /**
     * 计算从x， y到n,m的步数
     * @param x 移动的行坐标
     * @param y 移动的列坐标
     * @param n 总行数
     * @param m 总列数
     * @param stepsTaken 已经走过的步数
     * @return 从 x,y  走到 n,m 所需要的总步数
     */
    private static int getSteps(int x, int y, int stepsTaken, int[][] matric){
        int n = matric.length;
        int m = matric[0].length;

        // base case
        if (x < 0 || x > n -1 || y <0 || y > m -1) {
            return Integer.MAX_VALUE;
        } else if (x == n-1 && y == m-1) {
            return stepsTaken;
        }


        int curStepChoice1 = caculateCurStep(matric, x, y , x + 1,y);
        int choice1 = getSteps(x+1, y  ,stepsTaken + curStepChoice1, matric);

        int curStepChoice2 = caculateCurStep(matric, x, y , x,y + 1);
        int choice2 = getSteps(x, y+1 ,stepsTaken + curStepChoice2, matric);

//        int curStepChoice3 = caculateCurStep(matric, x, y , x ,y-1, n, m);
//        int choice3 = getSteps(x, y-1 ,n ,m ,stepsTaken + curStepChoice3, matric);

//        return Math.min(Math.min(choice1,choice2), choice3);
        return Math.min(choice1,choice2);
    }


    private static int getStepsWithDp(int x, int y, int[][] matric){

        int n = matric.length;
        int m = matric[0].length;

        int[][] dp = new int[n][m];
        dp[0][0] = 0;

        for (int i = 0; i < n ; i++) {
            for (int j = 0; j < m ; j++) {
                if (i == 0 && j == 0 )
                    continue;
                int choice1 = Integer.MAX_VALUE;
                int choice2 = Integer.MAX_VALUE;

                if (i > 0) {
                    int curStepChoice1 = caculateCurStep(matric, i - 1, j , i ,j);
                    choice1 = dp[i-1][j] + curStepChoice1;
                }


                if (j > 0) {
                    int curStepChoice2 = caculateCurStep(matric, i, j - 1 , i,j);
                    choice2 = dp[i][j-1] + curStepChoice2;
                }

                dp[i][j] = Math.min(choice1,choice2);
            }
        }


        return dp[x-1][y-1];
    }



    /**
     * 当前挪动异步，需要累加的步数
     * @param matric
     * @param x
     * @param y
     * @param nextStepX
     * @param nextStepY
     * @return
     */
    private static int caculateCurStep(int[][] matric, int x, int y, int nextStepX, int nextStepY) {

        int n = matric.length;
        int m = matric[0].length;

        if (nextStepX < 0 || nextStepX > n -1 || nextStepY < 0 || nextStepY > m -1) {
            return Integer.MAX_VALUE;
        }
        System.out.printf("x->%d, y->%d, nextStepX->%d, nextStepY->%d", x,y,nextStepX, nextStepY);
        System.out.println();
        if (matric[x][y] == matric[nextStepX][nextStepY]) {
            return 1;
        }else {
            return 2;
        }
    }

    /**
     * 问题分析
     * 题目要求从矩阵左上角(0,0)走到右下角(n-1,m-1)，可以向右、向左或向下移动。移动时的花费规则：
     *
     * 相同地形移动(沼泽→沼泽或平地→平地)：花费1单位时间
     *
     * 不同地形移动(沼泽→平地或平地→沼泽)：花费2单位时间
     *
     * 原始代码使用了暴力递归方法，这会存在大量重复计算，效率很低。
     *
     * 动态规划优化思路
     * 状态定义：dp[i][j] 表示从起点(0,0)到达位置(i,j)的最小时间花费
     *
     * 状态转移：
     *
     * 可以从上方(i-1,j)下来
     *
     * 可以从左边(i,j-1)过来
     *
     * 可以从右边(i,j+1)过来（注意边界条件）
     *
     * 初始化：dp[0][0] = 0
     *
     * 计算顺序：按行或按列顺序计算，可能需要多次迭代以确保收敛
     *
     * -----以下代码由deep seek 生成-----
     *
     * 优化说明
     * 时间复杂度：从指数级的递归降为O(n*m*k)，其中k是迭代次数(通常k <= n*m)
     *
     * 空间复杂度：O(n*m)用于存储dp数组
     *
     * 改进点：
     *
     * 使用动态规划表避免重复计算
     *
     * 采用类似Bellman-Ford算法的多次松弛方法处理向左移动的情况
     *
     * 设置最大迭代次数防止无限循环
     * @param matrix
     * @return
     */
    public static int minTimeToCross(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int n = matrix.length;
        int m = matrix[0].length;
        int[][] dp = new int[n][m];

        // 初始化dp数组为无穷大
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][0] = 0;  // 起点时间为0

        // 由于可能有向左移动，我们需要多次迭代确保收敛
        boolean updated;
        int iterations = 0;
        int maxIterations = n * m;  // 防止无限循环

        do {
            updated = false;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (i == 0 && j == 0) continue;  // 起点已经初始化

                    int minTime = Integer.MAX_VALUE;

                    // 检查上方
                    if (i > 0 && dp[i-1][j] != Integer.MAX_VALUE) {
                        int cost = (matrix[i-1][j] == matrix[i][j]) ? 1 : 2;
                        minTime = Math.min(minTime, dp[i-1][j] + cost);
                    }

                    // 检查左边
                    if (j > 0 && dp[i][j-1] != Integer.MAX_VALUE) {
                        int cost = (matrix[i][j-1] == matrix[i][j]) ? 1 : 2;
                        minTime = Math.min(minTime, dp[i][j-1] + cost);
                    }

                    // 检查右边
                    if (j < m-1 && dp[i][j+1] != Integer.MAX_VALUE) {
                        int cost = (matrix[i][j+1] == matrix[i][j]) ? 1 : 2;
                        minTime = Math.min(minTime, dp[i][j+1] + cost);
                    }

                    if (minTime < dp[i][j]) {
                        dp[i][j] = minTime;
                        updated = true;
                    }
                }
            }
            iterations++;
        } while (updated && iterations < maxIterations);

        return dp[n-1][m-1];
    }

}


